package com.acyouzi.leetcode.array;

import java.util.Stack;

/**
 * 17/9/21 22:32
 *
 * @author sunxu
 */
//https://leetcode.com/problems/next-greater-element-ii/description/
public class NextGreaterElementII {
  public static int[] nextGreaterElements(int[] nums) {
    int sum = nums.length;
    int[] res = new int[sum];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < sum*2; i++) {
      if (!stack.isEmpty() && nums[i % sum] > nums[stack.peek()]){
        res[stack.pop()] = nums[i%sum];
        i--;
      }else if (i < sum) stack.push(i);
    }
    while (!stack.isEmpty()){
      res[stack.pop()] = -1;
    }
    return res;
  }

  public static void main(String[] args) {
    nextGreaterElements(new int[]{-1,-1,-1,4,5});
  }
}
